﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Chapter_9__Recursion_
{
    class QuickSort
    {
        public static void Sort<T>(T[] array) where T : IComparable
        {
            quicksort(array, 0, array.Length - 1);
        }

        static void quicksort<T>(T[] array, int left, int right) where T : IComparable
        {
            int index = partition(array, left, right);
            if (left < index - 1)
            {
                quicksort(array, left, index - 1);
            }
            if (index < right)
            {
                quicksort(array, index, right);
            }
        }

        static int partition<T>(T[] array, int left, int right) where T : IComparable
        {
            T pivot = array[(left + right) / 2];  // Pick pivot point
            while (left <= right)
            { 
                // Find element on left that should be on right
                while (array[left].CompareTo(pivot) < 0) left++;

                // Find element on right that should be on left
                while (array[right].CompareTo(pivot) > 0) right--;

                // Swap elements, and move left and right indices
                if (left <= right)
                {
                    swap(array, left, right); // swaps elements
                    left++;
                    right--;
                }
            }

            return left;
        }

        static void swap<T>(T[] array, int index1, int index2)
        {
            T temp = array[index1];
            array[index1] = array[index2];
            array[index2] = temp;
        }
    }
}
